﻿namespace ClearLines.TspDemo.CSharp
{
   using System;
   using System.Collections.Generic;
   using System.Linq;

   public class Tsp
   {
      public static IList<City> Shuffle(Random rng, IList<City> cities)
      {
         var shuffled = new List<City>(cities);
         for (var i = cities.Count() - 1; i >= 1; i--)
         {
            var j = rng.Next(i + 1);
            var temp = shuffled[i];
            shuffled[i] = shuffled[j];
            shuffled[j] = temp;
         }

         return shuffled;
      }

      public static IList<City> Swap(Random rng, IList<City> cities)
      {
         var count = cities.Count();

         var swapped = new List<City>(cities);

         var first = rng.Next(count);
         var city = swapped[first];
         swapped.RemoveAt(first);

         var second = rng.Next(count);
         swapped.Insert(second, city);

         if (rng.NextDouble() < 0.1)
         {
            return Decross(rng, swapped);
         }

         return swapped;
      }

      public static double Length(IList<City> cities)
      {
         var length = 0d;
         for (var i = 0; i < cities.Count() - 1; i++)
         {
            length = length + Distance(cities[i], cities[i + 1]);
         }

         length = length + Distance(cities[cities.Count() - 1], cities[0]);
         return length;
      }

      public static double Distance(City city1, City city2)
      {
         return Math.Sqrt(
            Math.Pow((city1.X - city2.X), 2d) +
            Math.Pow((city1.Y - city2.Y), 2d));
      }

      public static IList<City> Decross(Random rng, IList<City> cities)
      {
         var count = cities.Count();

         var swapped = new List<City>(cities);

         var first = rng.Next(count - 3);         
         var city1 = swapped[first];
         var city2 = swapped[first + 1];

         for (var i = first + 2; i < count - 1; i++)
         {
            var city3 = swapped[i];
            var city4 = swapped[i + 1];
            if (HasIntersection(city1, city2, city3, city4))
            {
               swapped.Reverse(first + 1, i - first);
               break;
            }
         }

         return swapped;
      }

      public static bool HasIntersection(City city1, City city2, City city3, City city4)
      {
         var det1 = (city1.X - city3.X) * (city2.Y - city3.Y) - (city2.X - city3.X) * (city1.Y - city3.Y);
         var det2 = (city1.X - city4.X) * (city2.Y - city4.Y) - (city2.X - city4.X) * (city1.Y - city4.Y);

         var det3 = (city3.X - city1.X) * (city4.Y - city1.Y) - (city4.X - city1.X) * (city3.Y - city1.Y);
         var det4 = (city3.X - city2.X) * (city4.Y - city2.Y) - (city4.X - city2.X) * (city3.Y - city2.Y);

         return ((det1 * det2 <= 0d) && (det3 * det4 <= 0d));
      }
   }
}
